package com.sunny.l44;

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(null == preorder || null == inorder || preorder.length != inorder.length || 0 == preorder.length)
            return null;
        return buildCore(preorder, inorder, 0, 0, inorder.length-1);
    }
    public TreeNode buildCore(int[] preorder, int[] inorder, int ind, int left, int right){
        if(left > right)
            return null;
        if(left == right)
            return new TreeNode(preorder[ind]);

        int rootInd = getInd(inorder, preorder[ind], left, right);
        TreeNode root = new TreeNode(preorder[ind]);
        root.left = buildCore(preorder, inorder, ind+1, left, rootInd-1);
        root.right = buildCore(preorder, inorder, ind+(rootInd-left)+1, rootInd+1, right);
        return root;

    }
    public int getInd(int[] inorder, int val, int left, int right){
        int res = -1;
        for(int i=left;i<=right;i++){
            if(val == inorder[i]){
                res = i;
                break;
            }
        }
        return res;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
